package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/fair-candy-swap/'>公平的糖果交换(Fair Candy Swap)</a>
 * <p>爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。</p>
 * <p>两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。</p>
 * <p>返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：aliceSizes = [1,1], bobSizes = [2,2]
 *      输出：[1,2]
 *
 * 示例 2：
 *      输入：aliceSizes = [1,2], bobSizes = [2,3]
 *      输出：[1,2]
 *
 * 示例 3：
 *      输入：aliceSizes = [2], bobSizes = [1,3]
 *      输出：[2,3]
 *
 * 示例 4：
 *      输入：aliceSizes = [1,2,5], bobSizes = [2,4]
 *      输出：[5,4]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= aliceSizes.length, bobSizes.length <= 10^4</li>
 *         <li>1 <= aliceSizes[i], bobSizes[j] <= 10^5</li>
 *         <li>爱丽丝和鲍勃的糖果总数量不同。</li>
 *         <li>题目数据保证对于给定的输入至少存在一个有效答案。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/18 16:34
 */
public class LC0888FairCandySwap_S {
    static class Solution {
        public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
            int sumAlice = 0;
            int sumBob = 0;
            Set<Integer> aliceSizeSet = new HashSet<>();
            for (int aliceSize : aliceSizes) {
                sumAlice += aliceSize;
                aliceSizeSet.add(aliceSize);
            }
            for (int bobSize : bobSizes) {
                sumBob += bobSize;
            }
            if (sumAlice > sumBob) {
                // 此时 alice 应该给 bob:(sumAlice - sumBob)/2 个糖果
                int diff = (sumAlice - sumBob) >> 1;
                for (int bobSize : bobSizes) {
                    if (aliceSizeSet.contains(bobSize + diff)) {
                        return new int[]{bobSize + diff, bobSize};
                    }
                }
            } else {
                // 此时 bob 应该给 alice:(sumBob - sumAlice)/2 个糖果
                int diff = (sumBob - sumAlice) >> 1;
                for (int bobSize : bobSizes) {
                    if (aliceSizeSet.contains(bobSize - diff)) {
                        return new int[]{bobSize - diff, bobSize};
                    }
                }
            }
            return new int[0];
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i : solution.fairCandySwap(new int[]{1, 1}, new int[]{2, 2})) {
            System.out.print(i + "   ");
        }
        System.out.println();
        for (int i : solution.fairCandySwap(new int[]{1, 2}, new int[]{2, 3})) {
            System.out.print(i + "   ");
        }
        System.out.println();
        for (int i : solution.fairCandySwap(new int[]{2}, new int[]{1, 3})) {
            System.out.print(i + "   ");
        }
        System.out.println();
        for (int i : solution.fairCandySwap(new int[]{1, 2, 5}, new int[]{2, 4})) {
            System.out.print(i + "   ");
        }
        System.out.println();
    }
}
